package org.example.day;

/**
 * @Description: TODO
 * @Author wyatt
 * @Data 2024/06/24 20:20
 */
//给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素
// 。
//
// 数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1
//。
//
//
//
// 示例 1:
//
//
//输入: nums = [1,2,1]
//输出: [2,-1,2]
//解释: 第一个 1 的下一个更大的数是 2；
//数字 2 找不到下一个更大的数；
//第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
//
//
// 示例 2:
//
//
//输入: nums = [1,2,3,4,3]
//输出: [2,3,4,-1,4]
//
//
//
//
// 提示:
//
//
// 1 <= nums.length <= 10⁴
// -10⁹ <= nums[i] <= 10⁹
//
//
// Related Topics 栈 数组 单调栈 👍 960 👎 0

public class Solution503 {

    public static void main(String[] args) {
        int[] nums = new Solution503().nextGreaterElements(new int[]{1,2,2,2,2,2,2,2,2,2,2,2,100});
        for (int num : nums) {
            System.out.println(num);
        }
    }

    public int[] nextGreaterElements(int[] nums) {
        int[] next = new int[nums.length];
        int max = Integer.MIN_VALUE;

        for (int num : nums) {
            max = Math.max(max, num);
        }

        for (int i = 0; i < nums.length; i++) {

            if(nums[i] == max){
                next[i] = -1;
            }else {
                int j = i == nums.length - 1 ? 0 : i+1;
                while(nums[j] <= nums[i]){
                    j++;
                    if(j>=nums.length){
                        j=0;
                    }
                }
                next[i] = nums[j];
            }
        }

        return next;
    }

}
